package leetcode

import kotlinetc.println

//https://leetcode.com/problems/multiply-strings/

/**
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
Accepted  202,155  ; Submissions  658,077
 */
fun main(args: Array<String>) {


    48.toChar().println()
    //"121932631112635269"
    multiply("123456789",
            "987654321").println()
}

/**
 * 错位相加
 *              1 2 3
 *              4 5 6
 *                1 8
 *              1 2
 *              6
 *              1 5
 *            1 0
 *            5
 *            1 2
 *            8
 *          4
 *          -------------------
 *          5 6 0 8 8
 */
fun multiply(num1: String, num2: String): String {

    if (num1 == "0" || num2 == "0")
        return "0"

    val m = num1.length
    val n = num2.length


    val result = Array(m + n) { 0 }


    for (i in m - 1 downTo 0) {
        for (j in n - 1 downTo 0) {
            val k = i + j
            val s = (num1[i].toInt() - 48) * (num2[j].toInt() - 48) + result[k + 1]   //'0' = 48
            result[k + 1] = s % 10
            if (s >= 10) { //进位
                result[k] += s / 10
            }
        }
    }

    if (result[0] == 0)
        return String(result.drop(1).map { (it + 48).toChar() }.toCharArray())
    return String(result.map { (it + 48).toChar() }.toCharArray())

}